package logbrowse;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LogEntryDiff {
	public static LogEntryDiff compute(String code0, String code1) {
		String[] s = code0.split("\n");
		String[] t = code1.split("\n");
		int m = s.length;
		int n = t.length;
		int[][] d = new int[m + 1][n + 1];
		int[][] ops = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) { // deletion
			d[i][0] = i;
			ops[i][0] = 1;
		}
		for (int j = 0; j <= n; j++) { // insertion
			d[0][j] = j;
			ops[0][j] = 2;
		}
		for (int j = 1; j <= n; j++) {
			for (int i = 1; i <= m; i++) {
				String a = s[i - 1];
				String b = t[j - 1];
				if (a.equals(b)) {
					d[i][j] = d[i - 1][j - 1];
					ops[i][j] = 0;
				} else {
					int x = d[i - 1][j]; // deletion
					int y = d[i][j - 1]; // insertion
					int z = d[i - 1][j - 1]; // substitution
					int min;
					if (y < z) {
						min = x < y ? x : y;
					} else {
						min = x < z ? x : z;
					}
					d[i][j] = min + 1;
					if (min == x) {
						ops[i][j] = 1;
					} else if (min == y) {
						ops[i][j] = 2;
					} else if (min == z) {
						ops[i][j] = 3;
					}
				}
			}
		}

		ArrayList<Integer> dels = new ArrayList<Integer>();
		ArrayList<Integer> adds = new ArrayList<Integer>();
		ArrayList<Integer> modsS = new ArrayList<Integer>();
		ArrayList<Integer> modsT = new ArrayList<Integer>();
		
		int i = s.length;
		int j = t.length;
		while ((i > 0 || j > 0) && i >= 0 && j >= 0) {
			switch(ops[i][j]) {
			case 0: i--; j--; break;
			case 1: i--; dels.add(i); break;
			case 2: j--; adds.add(j); break;
			case 3: i--; j--; modsS.add(i); modsT.add(j); break;
			default: i--; j--; // should never happen
			}
		}
		return new LogEntryDiff(dels, adds, modsS, modsT);
	}

	private int dist;
	private List<Integer> deletions;
	private List<Integer> insertions;
	private List<Integer> changesSource;
	private List<Integer> changesDest;
	
	private LogEntryDiff(List<Integer> dels, List<Integer> adds, List<Integer> modsS,
			List<Integer> modsT) {
		dist = dels.size() + adds.size() + modsS.size();
		deletions = Collections.unmodifiableList(dels);
		insertions = Collections.unmodifiableList(adds);
		changesSource = Collections.unmodifiableList(modsS);
		changesDest = Collections.unmodifiableList(modsT);
	}
	
	public int getDistance() {
		return dist;
	}
	
	public List<Integer> getDeletions() {
		return deletions;
	}
	
	public List<Integer> getInsertions() {
		return insertions;
	}
	
	public List<Integer> getChangesSource() {
		return changesSource;
	}
	
	public List<Integer> getChangesDest() {
		return changesDest;
	}
}
